#include <iostream>
#include <vector>
#include <BinaryTree.hpp>
#include <Vector.hpp>

using namespace std;

class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        if(root == nullptr)
            return {};
        vector<vector<int>> res;
        deque<TreeNode *> q;
        q.push_back(root);
        int level = 0;
        while (!q.empty())
        {
            res.push_back(vector<int>());
            int size = q.size();
            if (level % 2 == 0)
            {
                for (int i = 0; i < size; i++)
                {
                    if (q.front()->left != nullptr)
                        q.push_back(q.front()->left);
                    if (q.front()->right != nullptr)
                        q.push_back(q.front()->right);
                    res[level].push_back(q.front()->val);
                    q.pop_front();
                }
            }
            else
            {
                for (int i = 0; i < size; i++)
                {
                    if (q.back()->right != nullptr)
                        q.push_front(q.back()->right);
                    if (q.back()->left != nullptr)
                        q.push_front(q.back()->left);
                    res[level].push_back(q.back()->val);
                    q.pop_back();
                }
            }
            level++;
        }
        return res;
    }
};
int main()
{
    cout << "Code103" << endl;
    Solution s;
    TreeNode *root = CreatTree("[3,9,20,null,null,15,7]", "null");
    auto res = s.zigzagLevelOrder(root);
    Print2DVector(res);
    return 0;
}